1. Field of the Invention
The present invention relates to a real time operating system kernel, and in particular to a method for implementing an event transfer system of a real time operating system kernel.
2. Description of the Background Art
Most operating systems are capable of supporting a multi-tasking feature that a plurality of tasks are concurrently executed in accordance with a user's program for an efficient use of a system. A kernel is the core program of the operating system and is run generally in the privileged mode of the system, invoked by interrupts or system calls. In addition, the above-described kernel is composed of the essential and primitive functions of an operating system such as generation and scheduling of the tasks, communication and synchronization between tasks, basic memory management, interrupt services, and device driver interfaces, etc. The characteristics and performance of the operating system are basically dependent on the kernel.
The real time operating system is adapted to a system in which certain tasks need to be executed in real time. The kernel should assure the real time task to be carried out in a certain dead-line. Therefore, the real time operating system kernel uses a preemptive scheduling mechanism generally based on a priority order.
The communication and synchronization between the tasks are important functions for the scheduling method and its performance and are implemented as a transfer system of events such as a message transfer between tasks using the queue, and the semaphore management for the mutual exclusion and synchronization between tasks. This event transfer system must be designed and implemented based on a minimization and optimization of a reaction time and on a priority-based preemptive scheduling.
In addition, since most of systems which require real time characteristics are embedded systems it is needed to reduce unnecessary functionalities and architecture of the systems and to implement the core functions that guarantee simple and effective operations.
As a solution for satisfying the above-described requirements, there can be the methods using a waiting-list to define and implement the relationship is between an event and the tasks trying to obtain it.
The known event transfer system implementation method of an operating system kernel which uses a waiting-list will be explained with reference to the accompanying drawings.
FIG. 1 is a view illustrating an example of the state of the tasks in a waiting-list of an event in the case that the known event transfer system implementation method for an operating system kernel is adapted.
As shown in FIG. 1, the first task (task 1) has a role of repeating event sending (transfer) to the event control block ECB1 of a message queue. The priority values of the first task, and second through fourth tasks 2-4 that repeat event reception are 40, 30, 20 and 20, respectively, (the lower value has the higher priority), and the second through fourth tasks 2-4 try to receive event value from a buffer of the event control block ECB1 of the first task.
When the first task (sender task), the event control block 1 of the first task, and the second through fourth tasks 2-4 are sequentially created and started to execute at a certain time interval, first of all, the first task is created and started to execute, and then the first task creates the event control block 1.
The event control block is a real structure of an event and is formed of a data structure managed by the kernel. Creating an event control block means that a task creates an event of its own. In the case that the second task 2 with the priority higher than that of the first task is created and started to execute and the second task 2 calls the kernel system function of waiting for (receiving) an event, then since the first task transfers no event yet, the second task 2 is blocked to the wait state waiting for the event to be transferred (sent) and is queued into the waiting-list of the event control block 1.
By the same reason, even though the third and fourth tasks 3 and 4 also have the higher priorities, the third and fourth tasks 3 and 4 are blocked respectively to the wait state waiting for the event and are queued into the waiting-list.
Thereafter, when the first task starts to send the event, at first the second task receives the event, is woken up and is resumed execution. Namely, the event is first transferred to the second task 2 first queued to the waiting-list based on the FIFO (First-In-First-Out), so that the second task is executed. Therefore, it causes the third and fourth tasks 3 and 4 having relatively higher priorities not to be first performed. Namely, the above-described method may be adapted to a known round robin scheduling method, but it may not satisfy the scheduling mechanism which supports real time characteristics.
In order to overcome the above-described problem, the structure of the waiting-list should be formed in a doubly linked list, and when an event is sent, the task with the highest priority should be searched in the waiting-list and resumed to execute. However, in this case, since it is not until an event is sent that the searching of the waiting-list is performed, it may take more reaction-time. And the more number of the tasks waiting for the event, the more time it takes also.